Error correcting codes play a vital role in communication, computer, and storage systems by ensuring the integrity of data. This invention pertains to the class of error correcting codes known as low-density parity-check (LDPC) codes and their iterative message-passing decoding algorithms. LDPC codes have gained prominence due to their ability to approach the information-theoretic channel capacity in the limit of infinite codeword length. They are standardized in a number of applications including wireless communications, satellite communications, deep-space communications, optical communications, as well as in storage systems such as solid state drives and hard disk drives. More recently, they have been gaining prominence for NAND flash memory applications due to the increasing densities of flash memories. All these applications are considered within the scope of use of this present invention.
A binary LDPC code is defined by a parity-check matrix (PCM) H that has N columns and M rows along with its corresponding Tanner graph G. The Tanner graph G is a bipartite graph consisting of a set of variable nodes V={v1, v2, . . . , vN} of cardinality N, and a set of check nodes C={c1, c2, . . . , cM} of cardinality M, that are connected by edges where an edge exists between nodes ci and vj if the matrix element in the parity-check matrix is equal to Hi,j=1. The weight of a column (or row) in H is the number of non-zero values iti contains. The degree of a variable node (or check node) is the number of its neighbors which is equal to the weight of its corresponding column (or row) in H. Therefore, the degree of a variable node vj will be equal to the weight of the j-th column of the parity-check matrix and the degree of a check node ci will be equal to the weight of the i-th row. An LDPC code is said to have fixed column weight dv if every column in H has weight dv, and variable column weight if there are at least two columns in H that have different weights. Similarly, an LDPC code is said to have fixed row weight dc if every row in H has weight dc. An example of a parity-check matrix is given in Eq. 1 below.
                    H        =                  (                                                    1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                                                    0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                                                    0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                                                    0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                                                    0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            1                                                                    1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                                                    0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                                                    0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                                                    0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                                                    0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                                                    1                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                                                    0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                                                    0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                                                    0                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                                                    0                                            0                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                            1                                            0                                            0                                            0                                              )                                    (        1        )            
A codeword of an LDPC code, x=(x1, x2, . . . , xN), is sent over a channel that could either be a communication channel or a data storage medium that stores the codeword. A value xi in the codeword is the binary value associated with the variable node vi in G. The channel vector y=(y1, y2, . . . , yN), is the vector that is computed based on the received vector r from the channel which may be different from x due to errors introduced by the channel. For example, in the specific case of the Binary Symmetric Channel (BSC), r=x+e, where + denotes an exclusive OR (XOR) operation, and the elements of the vector e represent errors introduced by flipping the codeword bits in x with probability α. The values yi∈γ referred to as channel values in this disclosure belong to a channel output alphabet γ. The vector y is input to the iterative decoder in order to recover x.
The present invention is applicable to the BSC and also for more general classes of channels which have larger channel output alphabets like for example the quantized additive white Gaussian noise (AWGN) channel. For the case of BSC which has only two possible channel outputs, γ may be defined as γ={±1} where by convention, +1 corresponds to the received bit value of 0, and −1 corresponds to a received bit value of 1. For the case of larger channel output alphabets, γ can be defined as γ={±1, ±2, . . . ±q}, if the number of possible channel outputs is even and equal to 2q or γ={0, ±1, ±2, . . . ±q} if the number of possible channel outputs is odd and equal 2q+1.
In a more general setting, any channel output can be defined as γ={±Y1, ±Y2, . . . ±Yq} for even cardinality and γ={0, ±Y1, ±Y2, . . . ±Yq} for odd cardinality, for which the present invention may also be used. For this disclosure, if the elements of the channel vector y can only take two possible values, then the decoding is referred to as hard-decision decoding and y is referred to as hard-decision input. If the elements in vector y can take more than two possible values, then the decoding is referred to as soft-decision decoding and the input is referred to as soft-decision input. For soft decision decoding, y is said to be a nq-bit soft-decision input, with nq=┌ log2(2q)┐ in case of even cardinality, and nq=┌ log2(2q+1)┐ in case of odd cardinality. ┌x┐ is the smallest integer larger than x.
The embodiments of the present invention can be illustrated through the use of a Tanner graph G where the decoding involves iteratively passing messages along the edges of the graph. This type of decoding is referred to as message-passing decoding of an LDPC code. FIG. 1 shows an example of a Tanner graph for the LDPC code of Eq.1, where the circles represent the variable nodes and squares represent the check nodes. The decoder is initialized by inputting the channel vector y and then messages are iteratively passed between the variable nodes and check nodes along the edges of the graph G. The messages get updated each time they arrive at a node in a manner such that the outgoing message on a particular edge is computed based on all of the incoming messages of that node, excluding the incoming message of that particular edge. An iteration of decoding is performed when all nodes in the graph have been processed at least one time in a particular order of processing typically referred to as scheduling. At the end of each iteration and also during the processing of one iteration of decoding, estimates of the bit values {circumflex over (x)}i are computed for all variable nodes vi based on the messages they receive from their neighboring check nodes, and the channel values yi. The hard-decision estimates of bit values {circumflex over (x)}i are computed using a decision function Ψ and used to check whether the decoder has converged to a codeword by sending them to the validator which computes the syndrome of the vector {circumflex over (x)}. The syndrome is defined asH{circumflex over (x)}T=0(mod 2).  (2)where xT denotes the transposition of vector x. The elements of the syndrome vector are referred to as syndrome bits. The validator checks whether at a given check node, the corresponding hard-decision estimates of their neighboring variable nodes form an even parity, and such a check node is said to be satisfied else it is unsatisfied. If every check node is satisfied, then the syndrome is zero and the decoder has converged to a codeword. The iterative process continues until the decoder converges to a codeword or has reached a maximum number of iterations. A decoder is said to have failed if it does not converge to a codeword.
The embodiments of the present invention are further related to a class of iterative message-passing decoders called finite alphabet iterative decoders (FAIDs). In these decoders, the messages belong to a finite alphabet  which consists of a finite—typically small—number of levels. For the specific illustrative case where  has odd cardinality, the message alphabet is denoted ={0, ±Li: 1≤i≤s} where Li∈+ and Li>Lj for any i>j.
The variable node update function for a variable node of degree dv in a FAID is a pre-defined map Φv: γ×{}dv-1→ which in this disclosure is referred to as variable node (VN) map, or VN map that computes the outgoing message on a particular edge as a function of the dv−1 incoming messages at the node, excluding the incoming message on that particular edge, and the channel value yi. The variable node update function can be designed to improve the error-correction capability of the decoder. An example of a map Φv for a variable node of degree dv=3 is provided in Table 1 below. In this example, the VN Map has 7 possible levels, i.e. s=3, and we show only the VN Map corresponding to y=−Y, so that the table entries are Φv(−Y, m1, m2).
TABLE 1m2m1−L3−L2−L10+L1+L2+L3−L3−L3−L3−L3−L3−L3−L3−L1−L2−L3−L3−L3−L3−L2−L1+L1−L1−L3−L3−L2−L2−L1−L1+L10−L3−L3−L2−L100+L1+L1−L3−L2−L100+L1+L2+L2−L3−L1−L10+L1+L1+L3+L3−L1+L1+L1+L1+L2+L3+L3
Note that the VN map for the channel value y=+Y can be deduced from the one with channel value y=−Y by symmetry:Φv(Y,m1,m2)=−Φv(−Y,−m1,−m2)m1∈m2∈  (3)
The check node update function Φc used in FAID is similar to the function used in the min-sum decoder which is typically used in the state-of-the-art. Let the edges incident to a check node of degree dc be labeled from 1 to dc, referred to as edge indices, and let m1, . . . , mdc-1 denote the incoming messages to a check node with degree dc such that mk denotes the incoming message corresponding to the k-th edge index. Then, in order to compute the outgoing message from the check node corresponding to the dc-th edge index, Φc is given by
                                          Φ            c                    ⁡                      (                                          m                1                            ,              …              ⁢                                                          ,                              m                                                      d                    c                                    -                  1                                                      )                          =                              (                                          ∏                                  j                  =                  1                                                                      d                    c                                    -                  1                                            ⁢                                                          ⁢                              sgn                ⁡                                  (                                      m                    j                                    )                                                      )                    ⁢                                    min                              1                ≤                j                ≤                                                      d                    c                                    -                  1                                                      ⁢                                          (                                                                        m                    j                                                                    )                            .                                                          (        4        )            
It is worth noting that the main difference between FAID and state-of-the-art min-sum decoders (and its variants) is in the definition of Φv. It was shown that FAID can outperform traditional message-passing decoders in the error-floor region for the BSC and numerical results were presented for codes with variable node of degree dv=3. In addition, it was shown that multiple FAIDs with different VN maps can be employed to further improve the performance at the cost of higher complexity
Preferred embodiments of the present invention specifically focus on LDPC codes whose parity-check matrices are composed of blocks of sub-matrices, though the present invention is not limited to such codes. In these preferred embodiments, the parity check matrix H is organized in blocks, or sub-matrices, as defined in Eq. 5,
                    H        =                  (                                                                      II                                      1                    ,                    1                                                                                                I                                      1                    ,                    2                                                                              …                                                              II                                      1                    ,                                          N                      b                                                                                                                                            H                                      2                    ,                    1                                                                                                H                                      2                    ,                    2                                                                              …                                                              H                                      2                    ,                    N                                                                                                      ⋮                                            ⋮                                            ⋮                                            ⋮                                                                                      H                                                            M                      b                                        ,                    1                                                                                                H                                                            M                      b                                        ,                    2                                                                              …                                                              H                                                            M                      b                                        ,                                          N                      b                                                                                                    )                                    (        5        )            
wherein the sub-matrices Hi,j, 1≤i≤Mb, 1≤j≤Nb have equal vertical dimensions for any fixed j, and have equal horizontal dimensions for every fixed i.
A column block is referred to as an entire column of sub-matrix blocks of the parity-check matrix, and the column block index j refers to the j-th column block that consists of the sub-matrices {Hi,j, 1≤i≤Mb}. Similarly a row block is referred to as an entire row of sub-matrix blocks of the parity-check matrix, and the row block index i refers to the i-th row block that consists of the sub-matrices {Hi,j, 1≤j≤Nb}. The dimensions for the sub-matrices can be arbitrary, and for the case when the sub-matrices Hi,j are L×L square matrices, L can be arbitrary. In preferred embodiments of this disclosure, the sub-matrices Hi,j are L×L square matrices, and can be circulant permutation matrices (CPM), all-zero matrices, or sums of circulant permutation matrices. This type of sub-matrix is commonly used in the state-of-the-art, and have the particularity that they can be defined by their first row/column together with a procedure to generate the remaining rows/columns. In circulant permutation matrices, each row/column can be obtained by a circular (cyclic) shift of another row/column. The LDPC codes for which the parity-check matrices are organized in blocks that are circulant permutation matrices, are referred to as quasi-cyclic LDPC (QC-LDPC) codes.
A CPM is defined as the power of a primitive element of a cyclic group. The primitive element is defined, for example, by the L×L matrix, P, shown in Eq. 6 for L=8.
                    P        =                  (                                                    0                                            0                                            0                                            0                                            0                                            0                                            0                                            1                                                                    1                                            0                                            0                                            0                                            0                                            0                                            0                                            0                                                                    0                                            1                                            0                                            0                                            0                                            0                                            0                                            0                                                                    0                                            0                                            1                                            0                                            0                                            0                                            0                                            0                                                                    0                                            0                                            0                                            1                                            0                                            0                                            0                                            0                                                                    0                                            0                                            0                                            0                                            1                                            0                                            0                                            0                                                                    0                                            0                                            0                                            0                                            0                                            1                                            0                                            0                                                                    0                                            0                                            0                                            0                                            0                                            0                                            1                                            0                                              )                                    (        6        )            
As a result, a CPM Pk, with k∈{0, . . . , L−1} has the form of the identity matrix, shifted k positions to the left. Said otherwise, the row-index of the nonzero value of the first column of Pk, is k+1. The index k will be referred to in this disclosure as the CPM shift value. An example of a parity-check matrix for L=5, Mb=3 and Nb=5 composed of powers of CPMs is given in Eq. 7.
                    (                                            1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                                          0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                                          0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                                          0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                                          0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                                          1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                                          0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                                          0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                                          0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                                          0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                                          1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                                          0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                                          0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                                          0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                                          0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      )                            (        7        )            
In this disclosure, a sub-matrix Hi,j is referred to as a null sub-matrix if Hi,j is an all-zero sub-matrix, else it is a non-null sub-matrix, and the number of non-null sub-matrices contained in a column block is referred to as column block degree. An example of a parity-check matrix containing null and non-null sub-matrices is shown in Eq. 8.
                    (                                            1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                                          0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                                          0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                                          0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                                          0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      1                                                          1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                                          0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                                          0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                                          0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                                          0                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                                          1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                                          0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                                          0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                                          0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                                          0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      0                                      0                                      0                                      0                                      1                                      0                                      0                                      1                                      0                                      0                                      0                                      )                            (        8        )            
Also relevant to this disclosure is the concept of layered decoding that is used to improve the decoder convergence speed while still maintaining a low hardware complexity. Layered LDPC decoding schemes effectively improve the convergence by reducing the required number of decoding iterations needed to reach successful decoding. A layered decoder produces messages from a subset of the check nodes to a subset of the variable nodes, followed by producing messages from a subset of the variable nodes to a subset of the check nodes. A layered decoder has a low resource utilization and requires low average number of iterations. For QC-LDPC codes, a row-layer is typically composed of L consecutive rows of the PCM, defined by a set of circulant permutation matrices. For example, the i-th row block in Eq. 5 defines the i-th row-layer. Similarly, a column-layer is composed of L consecutive columns of the PCM. For example, the j-th column block in Eq. 5 defines the j-th column-layer.
There are two main classes of layered decoding: row- or horizontal-layered decoding and column- or vertical-layered decoding. In horizontal-layered decoding, the parity check matrix of the LDPC code is subdivided into plurality of row layers, and the message updating is performed row layer by row layer. In vertical-layered decoding, the parity check matrix is partitioned into multiple column layers, and the message computation is performed column layer by column layer.
The concept of layers can be further extended to the concept of generalized row layer, for which the definition is:                A generalized row layer is defined as the concatenation of two or more row layers of the base matrix, such that in each column block of the generalized row layer, there is at most one non-null sub-matrix while its other blocks are null sub-matrices.        A full generalized row layer has further the property that each column block of the generalized row layer contains exactly one non-null sub-matrix.This definition ensures that for a QC-LDPC code with maximum column degree dv, the PCM can be structured with at least dv generalized row layers. For simplicity, and without loss of generality, we will assume in this disclosure that the number of generalized row layers is often equal to the maximum column degree dv. In a PCM that has a structure consisting of generalized row layers, the row blocks of each generalized row layer may be organized in an arbitrary order, and are not restricted to being only consecutive row layers in the PCM. Additionally, the number of row blocks in each generalized row layer could be different from one generalized row layer to another. The generalized row layer structure of the PCM provides the ability to perform processing of at least dv sub-matrices in parallel without data access conflicts.        
In spite of the prior art described above, there is still a strong need for LDPC decoders that can provide significantly lower error rate performance and operate at much higher throughputs while still maintaining a low hardware cost. One of the major problems with conventional LDPC decoders is the problem of error floor” where the decoders can not achieve a low enough error rate that is inadequate for many storage systems. Conventional approaches tend to use decoders that use large amounts of hardware resources and power to address the error floor problem and this increases further when high throughputs are required. Further, the hardware architectures of the decoder are required to be flexible so that the decoder can be tuned to particular conditions of the channel to achieve the best error rate performance. Also, previous literature and disclosures only focused on FAIDs for LDPC codes with fixed column-weight dv=3, which are not sufficiently strong in terms of error correction to be used in storage applications. This present invention aims to address all these issues.